05 - Hitra Fourierova transformacija (FFT)

Matematično-fizikalni praktikum, november 2023
Luka Skeledžija, 28201079

---

Uvod

Hitra Fourierova transformacija (FFT) je zelo uporabno orodje za analizo različnih vrst signalov. Njene prednosti vključujejo visoko hitrost in nizko porabo pomnilnika. Ti dve lastnosti nam omogočata analizo daljših signalov v primerjavi s standardno diskretno Fourierovo transformacijo (DFT). Z ustrezno implementacijo lahko zmanjšamo časovno zahtevnost iz $N^2$ na $N \log_2 N$, kar je za računalništvo bistvena pohitritev. Fourierove transformacije bomo uporabili za izračun (avto)korelacijskih funkcij, ki so definirane kot:

\begin{equation*} \phi_{gh}(\tau) = \frac{1}{T}\int\limits_0^{T} g(t+\tau)\,h(t)\,dt \>, \end{equation*} ali za diskretne vrednosti \begin{equation*} \phi_{gh}(n) = \frac{1}{N}\sum_{k=0}^{N-1} g_{k+n}\, h_k \>. \end{equation*}

Z uporabo Fourierovih transformacij lahko konvolucijo prevedemo v množenje. Naj bosta $F = \mathcal{F}(f)$ in $G = \mathcal{F}(g)$, nato je korelacijska funkcija podana kot: \begin{equation*} \phi_{gh}(n) = \frac{1}{N-n}\mathcal{F}^{-1} \left[ G \cdot (H)^\ast \right] \end{equation*} Za izračun avtokorelacijske funkcije uporabimo zgornjo enačbo, kjer je $g = h$. Avtokorelacijske funkcije nam bodo prišle prav pri analizi zašumljenih zvočnih signalov.

Naloga

Na spletni strani MF praktikuma najdeš posnetke oglašanja velike uharice, naše največje sove. Posneti sta dve sovi z minimalnim ozadjem (${\tt bubomono}$ in ${\tt bubo2mono}$) in nekaj mešanih signalov, ki zakrivajo njuno oglašanje (${\tt mix}$, ${\tt mix1}$, ${\tt mix2}$ in ${\tt mix22}$). V signalih ${\tt mix2}$ in ${\tt mix22}$ je oglašanje sove komaj še zaznavno. Izračunaj avtokorelacijsko funkcijo vseh signalov in poskusi ugotoviti, za katero sovo gre pri teh najbolj zašumljenih signalih!

Princip reševanja

1. Na podlagi posnetkov izrišemo spektrograme, da si vhodne podatke vizualiziramo.
2. Implementiramo autokorelacijsko funkcijo na različne načine in jih med sabo primerjamo.
3. Na podlagi zvočnih posnetkov izračunamo njihovo avtokorelacijsko funkcijo in skupaj z uporabo FFT poskusimo določiti sove v posnetkih.
4. Dodatek

Vhodni podatki in vizualizacija

V Python uvozimo .wav datoteke in jih pretvorimo v numpy array. Določili bomo namreč katera sova nastopa v določenem posnetku.

Datoteka	Opis	Vzorčenje [kHz]	Določena sova
bubo.wav	Velika uharica Simon	44.1	Simon (bubo)
bubo2.wav	Velika uharica Garfunkel	44.1	Garfunkel (bubo2)
mix.wav	Neznana uharica + čricki	44.1	?
mix1.wav	Neznana uharica + čricki + potok	44.1	?
mix2.wav	Neznana uharica + čricki + deroča reka	44.1	?
mix22.wav	Neznana uharica + deroča reka	44.1	?

Tabela 1: Vhodni podatki.

bubo.wav

bubo2.wav

mix.wav

mix1.wav

mix2.wav

mix22.wav

Spektrogram

Na podlagi prebranih posnetkov izrišemo spektrograme. Na prvem spektrogramu (bubo.wav) je skovik sove že na prvi pogled očiten, vendar za ostale posnetke ta sklep ni trivialen. Vseeno ugotovimo, da so iskani signali v rangu do $1\; \text{kHz}$ in vse bolj in bolj zašumljeni.

Avtokorelacijska funkcija

Ker imamo opravka z močno zašumljenimi signali, si bomo pri njihovi analizi pomagali z avtokorelacijsko funkcijo. Ker so naši posnetki vzorčeni z relativno visiko vzorčno frekvenco (44.1 kHz), moramo razmisliti o učinkoviti implementaciji. Avtokorelacijsko funkcijo implementiramo na 3 načine in jo testiramo na testnem zašumljenem signalu. Uporabimo 3 različne metode izračuna:

1. Po definiciji za diskretne vrednosti v jeziku Python: \begin{equation*} \phi_{hh}(n) = \frac{1}{N - n}\sum_{k=0}^{N-1} h_{k+n}\, h_k \>, \end{equation*}
2. Po definiciji z modifikacijo za numpy, kjer ima signal $h$ dolžine $N$ dodan "zero-padding" dolžine $N$, kar poimenujemo $\tilde{h}$ in zapišemo: \begin{equation*} \phi_{hh}(n) = \frac{1}{N - n}\sum_{k=0}^{2N-1} \tilde{h}_{k+n}\, \tilde{h}_k \>. \end{equation*}
3. Z uporabo FFT. Naj bo $H = \mathcal{F}(h)$, tedaj je korelacijska funkcija podana kot: \begin{equation*} \phi_{hh}(n) = \frac{1}{N-n}\mathcal{F}^{-1} \left[ \, \mid H \mid^2 \, \right] \end{equation*}

Test izvedemo na funkciji $f$, ki je sestavljena iz vsot in produktov elementarnih funkcij z dodanim šumom.

Iz rezultatov slutimo, da avtokorelacijska funkcija $f$ na nek način "izpovpreči" in tako odstrani šum. Vendar zgodba ni tako preprosta, saj obliki funkcij nista zares primerljivi. Iz primerjave časovne zahtevnosti ugotovimo, da je implementacija z uporabo FFT nekaj velikostnih redov hitrejša od ostalih dveh algoritmov. Odločimo se za uporabo FFT.

Analiza frekvenčnega spektra

Sove bomo verjetno najlažje razločili na podlagi frekvence skovika. Zato neobdelan posnetek z uporabo FFT pretvorimo v frekvenčni spekter. Ugotovimo, da so signali precej zašumljeni, šum pa je prisoten predvsem pri nižjih frekvencah. Kot smo ugotovili iz spektrogramov, nas zanima predvsem območje do 1 kHz. Iz prvih dveh jasnih posnetkov (bubo in bubo2) opazimo porast amplitude pri ~ 335 Hz in ~375 Hz. Vendar so nekateri signali še vedno preveč zašumljeni, da bi lahko sove zanesljivo ločili.

V nadaljevanju za zvočne posnetke izračunamo relativno avtokorelacijsko funkcijo

\begin{equation*} \widetilde{\phi}_{hh}(n) = { \phi_{hh}(n) - \langle h\rangle^2 \over \phi_{hh}(0) - \langle h\rangle^2 } \>, \end{equation*}

kjer je
\begin{equation*} \langle h\rangle = \frac{1}{N} \sum_{k=0}^{N-1} h_k \>. \end{equation*}

Na spodnjem grafu prikažemo $| \widetilde{\phi}_{hh} |$.

Ker si tudi iz tega grafa ne znamo pomagati, ponovno uporabimo FFT in avtokorelacijsko funkcijo pretvorimo v frekvenčni spekter.

Z uporabo avtokorelacije smo se precej uspešno znebili šuma. Še vedno pa nekatere "špice" (mix22) niso pretirano izrazite. Avtokorelacijo uporabimo še enkrat.

Na zadnjem grafu lahko končno zanesljivo razberemo frekvence skovikov, in sicer $(335 \pm 10) \; \text{Hz}$ za sovo Simona in $(375 \pm 10) \; \text{Hz}$ za Garfunkla. Na podlagi tega izpolnimo spodnjo tabelo in v vsakem posnetku določimo nastopajočo sovo.

Datoteka	Opis	Določena sova
bubo.wav	Velika uharica Simon	Simon (bubo)
bubo2.wav	Velika uharica Garfunkel	Garfunkel (bubo2)
mix.wav	Neznana uharica + čricki	Simon (bubo)
mix1.wav	Neznana uharica + čricki + potok	Simon (bubo)
mix2.wav	Neznana uharica + čricki + deroča reka	Simon (bubo)
mix22.wav	Neznana uharica + deroča reka	Garfunkel (bubo2)

Tabela 2: Rezultati analize zvoka.

Dodatek: S kakšno frekvenco prede Henry?

In the whimsical realm of quantum catodynamics, physicists have long pondered the enigmatic phenomenon of cat purring. According to the interstellar "Hitchhiker's Guide to the Galaxy," cats have been granted the rare ability to oscillate at a quantum frequency that transcends the boundaries of Schrödinger's box. It's not just a soothing sound; it's a cosmic symphony that defies the laws of physics as we know them. Some quantum quirk in the feline waveform allows cats to simultaneously purr and not purr, rendering them in a state of purrplexity, or what scientists affectionately refer to as "Schrödinger's Cat Purradox." It's a profound reminder that the universe is full of surprises, especially when it comes to our feline friends and their quantum serenades.

V dodatku poskusimo odgovoriti na dolgo pereče vprašanje... s kakšno frekvenco prede Henry?

cat.wav

Določena frekvenca $\nu_{\text{p}} = 130 \; \text{Hz} \; \pm \; 10 \; \text{Hz}$ Henryja uvršča med višje-frekvenčne predilce, saj se tipični spekter razpenja med 20 in 150 Hz.

Zaključek

Z uporabo FFT in izračunom funkcije avtokorelacije smo v frekvenčni sliki uspešno ločili med dvema signaloma različnih frekvenc tudi v najbolj zašumljenih primerih. Primerjali smo različne metode za izračun avtokorelacije in ugotovili, da je izračun s pomočjo FFT najbolj učinkovit.

---

Luka Skeledžija, Github source 🔗, 2023